package dynamicprogramming;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/4 23:00
 * https://leetcode-cn.com/problems/coin-change-2/
 */
public class Change {

    /**
     * dp[j]表示装满背包容量为j时方案个数
     * 地推公式：dp[j] += dp[j - coins[i]]
     * 初始化：
     * @param amount
     * @param coins
     * @return
     */
    public static int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        //物品个数
        for (int i = 0; i < coins.length; i++) {
            //背包容量
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
                System.out.println("i=" + i + " j：" + j + " dp[" + j + "]：" + dp[j]);
            }
        }
//        for (int j = 0; j <= amount; j++) { // 遍历背包容量
//            for (int i = 0; i < coins.length; i++) { // 遍历物品
//                if (j - coins[i] >= 0) {
//                    dp[j] += dp[j - coins[i]];
//                    System.out.println("i=" + i + " j：" + j + " dp[" + j + "]：" + dp[j]+" "+(j - coins[i]));
//                }
//            }
//        }
        return dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int change = change(5, coins);
        System.out.println(change);
    }
}
